package com.leo.leetcode.s100;

/**
 *
 * @author xuexiaolei
 * @version 2017年11月21日
 */
public class T35SearchInsertPosition {
    public static int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]>=target) return i;
        }
        return nums.length;
    }

    /**
     * 应该想到二分法！！
     * @param nums
     * @param target
     * @return
     */
    public static int searchInsert2(int[] nums, int target) {
        return searchPos(nums, 0, nums.length,target);
    }

    private static int searchPos(int[] nums, int begin, int end, int target) {
        int pos = (begin+end)/2;
        if (begin>=end || nums[pos] == target){
            return pos;
        }
        if (nums[pos] > target){
            return searchPos(nums, begin, pos-1, target);
        }else{
            return searchPos(nums, pos+1, end, target);
        }
    }

    public static void main(String[] args) {
        System.out.println(searchInsert(new int[]{},5));
        System.out.println(searchInsert(new int[]{1,3,5,6},5));
        System.out.println(searchInsert(new int[]{1,3,5,6},2));
        System.out.println(searchInsert(new int[]{1,3,5,6},7));
        System.out.println(searchInsert(new int[]{1,3,5,6},0));

        System.out.println("==========================");

        System.out.println(searchInsert2(new int[]{},5));
        System.out.println(searchInsert2(new int[]{1,3,5,6},5));
        System.out.println(searchInsert2(new int[]{1,3,5,6},2));
        System.out.println(searchInsert2(new int[]{1,3,5,6},7));
        System.out.println(searchInsert2(new int[]{1,3,5,6},0));
        System.out.println(searchInsert2(new int[]{1,3,5,6,7},9));
    }
}
